class Solution {

    //判断是否越界
    public boolean isMaze(int x, int y, int m, int n) {
        return 0 <= x && x < m && 0 <= y && y < n;
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;    //获取行列
        int curDir = 0, x = 0, y = 0;
        boolean[][] vis = new boolean[m][n];        //用于标记是否走过
        int[][] dirs = new int[][]{
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
        };

        for(int i = 0; i < m * n; i++) {
            switch(curDir) {    //按当前方位继续移动
                case 0:
                    vis[x][y] = true;
                    ans.add(matrix[x][y]);

                    //如果越界，或者下一个路径走过，我们就按顺序拐弯
                    if(!isMaze(x + dirs[curDir][0], y + dirs[curDir][1], m, n) || vis[x + dirs[curDir][0]][y + dirs[curDir][1]]) {
                        curDir = (curDir + 1) % 4;
                    }

                    x += dirs[curDir][0];
                    y += dirs[curDir][1];
                    break;
                case 1:
                    vis[x][y] = true;
                    ans.add(matrix[x][y]);

                    if(!isMaze(x + dirs[curDir][0], y + dirs[curDir][1], m, n) || vis[x + dirs[curDir][0]][y + dirs[curDir][1]]) {
                        curDir = (curDir + 1) % 4;
                    }

                    x += dirs[curDir][0];
                    y += dirs[curDir][1];
                    break;
                case 2:
                    vis[x][y] = true;
                    ans.add(matrix[x][y]);

                    if(!isMaze(x + dirs[curDir][0], y + dirs[curDir][1], m, n) || vis[x + dirs[curDir][0]][y + dirs[curDir][1]]) {
                        curDir = (curDir + 1) % 4;
                    }

                    x += dirs[curDir][0];
                    y += dirs[curDir][1];
                    break;
                case 3:
                    vis[x][y] = true;
                    ans.add(matrix[x][y]);

                    if(!isMaze(x + dirs[curDir][0], y + dirs[curDir][1], m, n) || vis[x + dirs[curDir][0]][y + dirs[curDir][1]]) {
                        curDir = (curDir + 1) % 4;
                    }

                    x += dirs[curDir][0];
                    y += dirs[curDir][1];
                    break;
            }
        }

        return ans;
    }
}